1．启发式搜索算法A

启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

评价函数的形式如下：

f(n)＝g(n)＋h(n)

其中n是被评价的节点。

f(n)、g(n)和h(n)各自表述什么含义呢？我们先来定义下面几个函数的含义，它们与f(n)、g(n)和h(n)的差别是都带有一个“*”号。

g*(n)：表示从初始节点s到节点n的最短路径的耗散值；

h*(n)：表示从节点n到目标节点g的最短路径的耗散值；

f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。

而f(n)、g(n)和h(n)则分别表示是对f*(n)、g*(n)和h*(n)三个函数值的的估计值。是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，总是选择当前f值最小的节点来优先扩展。

过程A

①OPEN:＝(s)，f(s):＝g(s)+h(s);

②LOOP: IF OPEN＝( ) THEN EXIT(FAIL)；

③n:＝FIRST(OPEN)；

④IF GOAL(n)THEN EXIT(SUCCESS)；

⑤REMOVE(n，OPEN)，ADD(n，CLOSED)；

⑥EXPAND(n)→{mi}，计算f(n，mi)＝g(n，mi)+h(mi)；g(n，mi)是从s通过n到mi的耗散值，f(n，mi)是从s通过n、mi到目标节点耗散值的估计。

·ADD(mj，OPEN)，标记mi到n的指针。

·IF f(n，mk)